package suanfaji;

import java.util.*;

public class HFmanTree {
    public Treejie tou;
    public Map<String,String> map;
    public Map<String,String> fanmap;
    public String erjinzhi;
    public String yuan;

    public HFmanTree() {
    }

    public HFmanTree(String yuan) {
        create(yuan);
        this.map=getbianma();
        this.fanmap=getbianma2(map);
        this.erjinzhi=getErJinZhi(fanmap,yuan);
        this.yuan=erZhuanString(erjinzhi,map);
    }

    /**
     * 创建一个哈夫曼树；
     * @param s
     */
    public void create(String s){
        List<Treejie> list=new ArrayList<>();
        Map<String,Integer> map=hfman(s);
        Set<String> set=map.keySet();
        for(String d:set){
            Treejie c=new Treejie(d,map.get(d));
            list.add(c);
        }
        while(list.size()!=1){
            kuaipai(list,0,list.size()-1);
            Treejie x=list.get(0);
            Treejie y=list.get(1);
            list.remove(0);
            list.remove(0);
            Treejie dai=new Treejie(x.shu+y.shu);
            dai.left=x;
            dai.right=y;
            list.add(dai);
        }
        tou=list.get(0);
    }

    /**
     * 将二进制数字转换为字符串
     * @param result
     * @param map
     * @return
     */
    public String erZhuanString(String result,Map<String,String> map){
        String hei="";
        String daan="";
        Map<String,String> map2=map;
        for(int i=0;i<result.length();i++){
            hei=hei+result.charAt(i);
            if(map2.containsKey(hei)){
                daan=daan+map2.get(hei);
                hei="";
            }
        }
        return daan;
    }

    /**
     * 得到一个二进制编码
     * @param map
     * @param ss
     * @return
     */
    public String getErJinZhi(Map<String,String> map,String ss){
        Map<String,String> map1=map;
        String result="";
        for(int i=0;i<ss.length();i++){
            result=result+map1.get(ss.charAt(i)+"");
        }
        return result;
    }

    /**
     * 得到一个字符与哈夫曼编码的对应关系
     * @return
     */
    public Map<String,String> getbianma(){
        Treejie zhegeshu=this.tou;
        Map<String,String> map=new HashMap<>();
        String b="";
        biali(zhegeshu,map,b);
        return map;
    }

    /**
     * 得到一个字符与哈夫曼编码的反过来的对应关系
     * @param map
     * @return
     */
    public Map<String,String> getbianma2(Map<String,String> map){
        Set<Map.Entry<String, String>> entries = map.entrySet();
        Map<String,String> map1=new HashMap<>();
        for(Map.Entry<String, String> s:entries){
            map1.put(s.getValue(),s.getKey());
        }
        return map1;
    }
    private static void biali(Treejie t, Map<String, String> map, String b){
        if(t.left==null && t.right==null){
            map.put(b, t.value);
            return;
        }
        if(t.left!=null){
            biali(t.left,map,b+"0");
        }
        if (t.right!=null ){
            biali(t.right,map,b+"1");
        }
    }
    private static void kuaipai(List<Treejie> list, int left, int right){
        int i=left;
        int j=right;
        if(left>right){
            return;
        }
        Treejie temp=list.get(left);

        while(i!=j){
            while(list.get(j).shu>=temp.shu && i<j){
                j--;
            }
            while(list.get(i).shu<=temp.shu && i<j){
                i++;
            }
            Treejie mid=list.get(j);
            Treejie mid2=list.get(i);
            list.set(j,mid2);
            list.set(i,mid);
        }
        Treejie zan=list.get(i);
        list.set(left,zan);
        list.set(i,temp);
        kuaipai(list,left,j-1);
        kuaipai(list,j+1,right);
    }
    private static Map<String,Integer> hfman(String s){
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i)+"")){
                int re= map.get(s.charAt(i)+"");
                map.put(s.charAt(i)+"",re+1);
            }else{
                map.put(s.charAt(i)+"",1);
            }
        }
        return map;
    }
    public static void main(String[] args) {
        HFmanTree tree=new HFmanTree("sdfcvxgrsdfwerwrgsadddaqqwegx");
        System.out.println(tree.erjinzhi);
        System.out.println(tree.fanmap);
        System.out.println(tree.yuan);

    }
}
